#include <iostream>
#include <vector>
#include <string>
void getNextArray(std::string& s, std::vector<int>& arr)
{
	int j = 0; arr[0] = 0;
	for (int i = 1; i < arr.size(); ++i)
	{
		while (j > 0 && s[i] != s[j])
		{
			j = arr[j - 1];
		}
		if (s[i] == s[j])
		{
			j++;
		}
		arr[i] = j;
	}
	
}

//test
int main()
{
	std::string s = "abaababbaa";
	int len = s.size();
	std::vector<int> v(len, 0);
	getNextArray(s, v);
	for (int i = 0; i < len; ++i)
	{
		std::cout << v[i] << " ";
	}
	std::cout << std::endl;
	return 0;
}